package leetcode;

import java.util.HashSet;

import common.ListNode;

/**
 * 环形链表 II  
 */
public class LeetCode142 {
    /**
     * 通过Hash解决
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     * @param head
     * @return
     */
    public ListNode detectCycle1(ListNode head) {
        HashSet<ListNode> visited = new HashSet<>();
        while (head != null) {
            if (visited.contains(head)) return head;
            visited.add(head);
            head = head.next;
        }
        return null;
    }

    /**
     * 通过快慢指针解决
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        // step 1 判断是否有环 没有直接返回NULL
        ListNode fast = head.next, slow = head;
        boolean isLoop = false;
        while (fast != null && fast.next != null) {
            if (fast == slow) {
                isLoop = true;
                break;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        if (!isLoop) return null;
        // step 2 计算环的大小
        int loopSize = 1;
        while ((fast = fast.next.next) != (slow = slow.next)) loopSize++;
        // step 3 计算环入口位置
        fast = slow = head;
        for (int i = 0; i < loopSize; i++) fast = fast.next;
        while ((slow != fast) && (slow = slow.next) != (fast = fast.next)) ;
        return slow;
    }

    
}